package MyStack;

import java.util.Stack;

public class Test01 {
    public static void main1(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.peek());
        boolean empty = stack.empty();
        System.out.println(empty);
    }

    public static void main2(String[] args) {
        MyStack stack = new MyStack();
        stack.push(21);
        stack.push(34);
        stack.push(56);
        stack.push(67);
        int val = stack.pop();
        System.out.println(val);
        val = stack.peek();
        System.out.println(val);
        boolean empty = stack.isEmpty();
        System.out.println(empty);
    }

    public int evalRPN (String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (!isOperator(s)) {
                Integer ret = Integer.valueOf(s);
                stack.push(ret);
            } else {
                Integer val2 = stack.pop();
                Integer val1 = stack.pop();
                switch(s) {
                    case "+":
                        stack.push(val1 + val2);
                        break;
                    case "-":
                        stack.push(val1 - val2);
                        break;
                    case "*":
                        stack.push(val1 * val2);
                        break;
                    case "/":
                        stack.push(val1 / val2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isOperator(String s) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            return true;
        }
        return false;
    }

    //括号匹配问题 字符串遍历完成并且栈为空 力扣20
    //1.左右括号不匹配（{）}
    //2.字符串遍历完成了但栈不为空 （（）
    //3.字符串没有遍历完成但是栈为空
    //思路：遇到左括号入栈 ， 遇到右括号查看栈顶元素和当前右括号是否匹配

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch =='[') {
                stack.push(ch);
            } else {
                //如果为右括号 ， 判断栈是否为空
                if (stack.isEmpty()) {
                    return false;
                }
                char peekch = stack.peek();
                if (peekch == '(' && ch == ')'
                || peekch == '{' && ch == '}'
                ||peekch == '[' && ch == ']') {
                    stack.pop();
                } else {
                    return false;
                }

            }

        }
        //匹配完成队列不为空
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }

    public static boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch =='[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else {
                    char peekch = stack.peek();
                    if (peekch == '(' && ch == ')'
                    || peekch == '{' && ch == '}'
                    || peekch == '[' && ch == ']') {
                        stack.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        if (!stack.isEmpty()) {

        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(isValid("(({})"));
    }

    //出栈入栈次序匹配问题
    //栈的压入 ， 弹出序列 牛客 JZ31
    //遍历 pushV 数组 ， 每次入栈后 ， 拿 popV 数组的 j 位置的元素比较 ， 是否一样 ， 如果一样则要除栈
    //同时让 j++ 继续往后走
    //再次判断当前栈顶元素和 j 下标元素值是否相同 ， 如果一样继续出 ， 如果不一样就继续入栈
    //如果栈为空 ， 并且 j 遍历完成了 popV 数组 ， 返回 true
    public boolean IsPopOrder (int[] pushV , int[] popV) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < pushV.length; i++) {
            int j = 0;
            while(!stack.isEmpty() && j < popV.length
                    && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

    //最小栈 力扣155 时间复杂度O(1)
    //用两个栈来操作 stack minStack（元素实时更新 ， 同步实时维护最小值）
    //push 普通栈一定要维护；如果是第一次 push 那么最小栈要维护； 如果最小栈不为空 ， 那么需要判断当前存放的元素是不是比最小栈顶元素小 ，如果小则放！
    //getMin() 每次拿最小栈的栈顶元素
    //pop() 如果弹出的元素不是不是最小栈的栈顶元素 ， 那么只需要弹出普通栈即可 ， 相反也要弹出普通栈的栈顶元素
    //top() 知识获取普通栈的栈顶元素不弹出
    class Minstack {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();
        public Minstack() {

        }
        public void push( int val) {
            stack.push(val);
            if (minStack.isEmpty()) {
                stack.push(val);
            } else {
                if (val <= minStack.peek()) {
                    minStack.push(val);
                }
            }
        }

        public void pop() {
            int val = stack.pop();
            if (val == minStack.peek()) {
                minStack.pop();
            }
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
}
